{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #将二叉搜索树转化为排序的双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #linked-list #binary-tree #doubly-linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #链表 #二叉树 #双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: treeToDoublyList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将二叉搜索树转化为排序的双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>将一个 <strong>二叉搜索树</strong> 就地转化为一个 <strong>已排序的双向循环链表</strong> 。</p>\n",
    "\n",
    "<p>对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。</p>\n",
    "\n",
    "<p>特别地，我们希望可以 <strong>就地</strong> 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,5,1,3] \n",
    "\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/12/bstdllreturndll.png\" />\n",
    "<strong>输出：</strong>[1,2,3,4,5]\n",
    "\n",
    "<strong>解释：</strong>下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/12/bstdllreturnbst.png\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>输入是空树，所以输出也是空链表。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li><code>Node.left.val &lt; Node.val &lt; Node.right.val</code></li>\n",
    "\t<li><code>Node.val</code> 的所有值都是独一无二的</li>\n",
    "\t<li><code>0 &lt;= Number of Nodes &lt;= 2000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 426 题相同：<a href=\"https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/\" rel=\"noopener noreferrer\" target=\"_blank\">https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof](https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof](https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,1,3]', '[2,1,3]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = []\n",
    "        while root:\n",
    "            stack.append(root)\n",
    "            root = root.left\n",
    "        pre, head = None, stack[-1]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.right:\n",
    "                cur = node.right\n",
    "                while cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "            node.left = pre\n",
    "            if pre:\n",
    "                pre.right = node\n",
    "            pre = node\n",
    "        node.right, head.left = head, node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return \n",
    "        stack = []\n",
    "        cur = root\n",
    "\n",
    "        while cur:\n",
    "            stack.append(cur)\n",
    "            cur = cur.left\n",
    "        head = cur = stack.pop()\n",
    "        pre = cur\n",
    "        cur = cur.right\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                pre.right = cur\n",
    "                cur.left = pre\n",
    "                \n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "        \n",
    "        pre.right = head\n",
    "        head.left = pre\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "# class dualLinkNode:\n",
    "#     def __init__(self, val, prev = None, next = None):\n",
    "#         self.val = val\n",
    "#         self.prev = prev\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        pre, cur = None, root\n",
    "        head = None\n",
    "        stack = []\n",
    "        while cur:\n",
    "            stack.append(cur)\n",
    "            # stack.append(cur)\n",
    "            cur = cur.left\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if pre:\n",
    "                pre.right = cur\n",
    "            else:\n",
    "                head = cur\n",
    "            cur.left = pre\n",
    "            # print(cur.val)\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "        # pre指向尾指针\n",
    "        head.left = pre\n",
    "        pre.right = head\n",
    "        return head\n",
    "\n",
    "        # self.pre, cur = None, root # 使用self. 将其转化为全局变量\n",
    "        # def dfs(root):\n",
    "        #     if not root:\n",
    "        #         return root\n",
    "            \n",
    "        #     dfs(root.left)\n",
    "        #     if self.pre:\n",
    "        #         self.pre.right = root\n",
    "        #     else:\n",
    "        #         self.head = root # pre为空则当前root节点为头节点\n",
    "        #     root.left = self.pre\n",
    "        #     self.pre = root\n",
    "        #     dfs(root.right)\n",
    "        \n",
    "        # dfs(cur)\n",
    "        # self.head.left = self.pre\n",
    "        # self.pre.right = self.head\n",
    "        # return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        stack=[]\n",
    "        if not root:\n",
    "            return root\n",
    "        num=0\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root=root.left\n",
    "            root=stack.pop()\n",
    "            num+=1\n",
    "            if num==1:\n",
    "                res=root\n",
    "                head=res\n",
    "            else:\n",
    "                res.right=root\n",
    "                root.left=res\n",
    "                res=res.right\n",
    "            root=root.right\n",
    "        res.right=head\n",
    "        head.left=res\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        stack = list()\n",
    "        if not root:\n",
    "            return root\n",
    "        p, preNode, head = root, None, None\n",
    "        while len(stack)>0 or p:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            q = stack.pop()\n",
    "            q.left = preNode\n",
    "            if not preNode:\n",
    "                head = q\n",
    "            else:\n",
    "                preNode.right = q\n",
    "            preNode = q\n",
    "            p = q.right\n",
    "\n",
    "        head.left = preNode\n",
    "        preNode.right = head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        # 要标记下head节点和最后一个节点，因为这两个是没办法在迭代或者变量的时候处理的\n",
    "        if not root: return root\n",
    "        head, pre = None, None\n",
    "        cur, stack = root, []  # 用户进行中序遍历\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            tmp = stack.pop()\n",
    "            if not pre:\n",
    "                head = tmp  # 记录下，这就是链表的头节点\n",
    "            else:\n",
    "                pre.right, tmp.left = tmp, pre\n",
    "            pre = tmp  # 更新pre节点\n",
    "            if tmp.right:\n",
    "                cur = tmp.right\n",
    "        # 处理头尾节点【尾节点就是现在的pre】\n",
    "        head.left, pre.right = pre, head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        pred_head = Node()\n",
    "        pred = pred_head\n",
    "        stack = []\n",
    "        val = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                left = root.left\n",
    "                root.left= None\n",
    "                stack.append(root)\n",
    "                root = left\n",
    "            root = stack.pop()\n",
    "            val.append(root.val)\n",
    "            pred.right = root\n",
    "            root.left = pred \n",
    "            pred = pred.right\n",
    "            root = root.right\n",
    "\n",
    "        pred.right  =pred_head.right\n",
    "        pred_head.right.left= pred\n",
    "        return pred_head.right\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        \n",
    "        pre, head = None, None\n",
    "        cur = root\n",
    "        stack = []\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if pre:\n",
    "                pre.right, cur.left = cur, pre\n",
    "            else:\n",
    "                head = cur\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "            \n",
    "        if not root:\n",
    "            return\n",
    "        head.left, pre.right = pre, head\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        head, pre = Node(), Node(1001)\n",
    "        head.right = pre\n",
    "        stack = []\n",
    "        cur = root\n",
    "        while stack or cur:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                \n",
    "                pre.right = cur\n",
    "                tmp = pre\n",
    "                pre = pre.right\n",
    "                pre.left = tmp\n",
    "                \n",
    "                cur = cur.right\n",
    "        pre.right = head.right.right\n",
    "        pre.right.left = pre\n",
    "        \n",
    "        return head.right.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        stack, index = [], -1\n",
    "        temp = root\n",
    "        while temp is not None:\n",
    "            stack.append(temp)\n",
    "            index += 1\n",
    "            temp = temp.left\n",
    "        head = stack[index]\n",
    "        while index != -1:\n",
    "            current = stack[index]\n",
    "            temp = current\n",
    "            index -= 1\n",
    "            if temp.right is not None:\n",
    "                temp = temp.right\n",
    "                while temp is not None:\n",
    "                    if index + 1 < len(stack):\n",
    "                        stack[index + 1] = temp\n",
    "                    else:\n",
    "                        stack.append(temp)\n",
    "                    index += 1\n",
    "                    temp = temp.left\n",
    "            if index != -1:\n",
    "                current.right = stack[index]\n",
    "                stack[index].left = current\n",
    "        current.right = head\n",
    "        head.left = current\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        stack = []\n",
    "        cur = root\n",
    "        head = None\n",
    "        pre  = None\n",
    "\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            if stack:\n",
    "                cur = stack.pop()\n",
    "            if pre:\n",
    "                pre.right = cur\n",
    "            else:\n",
    "                head = cur\n",
    "            \n",
    "            cur.left = pre\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "\n",
    "        head.left = pre\n",
    "        pre.right = head\n",
    "\n",
    "        return head  \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = []\n",
    "        head = Node(None)\n",
    "        pre = head\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            node = stack.pop()\n",
    "            pre.right = node\n",
    "            node.left = pre\n",
    "            pre = node\n",
    "            root = node.right\n",
    "        # cur = head\n",
    "        # while cur:\n",
    "        #     print(cur.val)\n",
    "        #     cur = cur.right\n",
    "        pre.right = head.right\n",
    "        head.right.left = pre\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        self.ans = []\n",
    "        q = []\n",
    "        s = root\n",
    "        while s or len(q) > 0:\n",
    "            while s:\n",
    "                q.append(s)\n",
    "                s = s.left\n",
    "            if len(q) > 0:\n",
    "                s = q.pop()\n",
    "                # visit\n",
    "                self.ans.append(s)\n",
    "                # \n",
    "                s = s.right\n",
    "\n",
    "        for i in range(len(self.ans) - 1):\n",
    "            self.ans[i].right = self.ans[i + 1]\n",
    "            self.ans[i + 1].left = self.ans[i]\n",
    "        self.ans[-1].right = self.ans[0]\n",
    "        self.ans[0].left = self.ans[-1]\n",
    "    \n",
    "        return self.ans[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        st = []\n",
    "        head, cur, tail = None, None, None\n",
    "        while st or root:\n",
    "            while root:\n",
    "                st.append(root)\n",
    "                root = root.left\n",
    "            t = st.pop()\n",
    "            # print(f't={t.val}')\n",
    "            tmp = t.right\n",
    "            if not head:\n",
    "                cur = t\n",
    "                head = cur\n",
    "            else:\n",
    "                cur.right = t\n",
    "                t.left = cur\n",
    "                cur = cur.right\n",
    "            if tmp:\n",
    "                root = tmp\n",
    "            tail = t\n",
    " \n",
    "        # print(f'{head.val}')\n",
    "        # print(f'{tail.val}')\n",
    "        if not head or not tail: return head\n",
    "        tail.right = head\n",
    "        head.left = tail\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        res=[]\n",
    "        stack=[]\n",
    "        p=root\n",
    "        while p or stack:\n",
    "            if p:\n",
    "                stack.append(p)\n",
    "                p=p.left\n",
    "            else:\n",
    "                p=stack.pop()\n",
    "                res.append(p)\n",
    "                p=p.right\n",
    "        head=Node(0)\n",
    "        for i in range(1,len(res)):\n",
    "            res[i-1].right=res[i]\n",
    "            res[i].left=res[i-1]\n",
    "        res[-1].right=res[0]\n",
    "        res[0].left=res[-1]\n",
    "        head.right=res[0]\n",
    "        return head.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return\n",
    "        dic = {}\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while stack or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                dic[i] = node\n",
    "                i += 1\n",
    "                root = node.right\n",
    "        for j in range(1, i):\n",
    "            dic[j-1].right = dic[j]\n",
    "            dic[j].left = dic[j-1]\n",
    "        dic[0].left = dic[i-1]\n",
    "        dic[i-1].right = dic[0]\n",
    "        return dic[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        #solution 1\n",
    "        # def helper(node):\n",
    "        #     nonlocal first,last\n",
    "        #     if not node: return\n",
    "        #     helper(node.left)\n",
    "        #     if last:\n",
    "        #         last.right = node\n",
    "        #         node.left = last\n",
    "        #     else:\n",
    "        #         last = node\n",
    "        #         first = node\n",
    "        #     last = node\n",
    "        #     helper(node.right)\n",
    "        #     return\n",
    "        # if not root: return None\n",
    "        # first = None\n",
    "        # last = None\n",
    "        # helper(root)\n",
    "        # first.left = last\n",
    "        # last.right = first\n",
    "        # return first\n",
    "\n",
    "        #solution 2\n",
    "        if not root: return None\n",
    "        stack = []\n",
    "        p = root\n",
    "        first = None\n",
    "        last = None\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            if last:\n",
    "                last.right = p\n",
    "                p.left = last\n",
    "            else:\n",
    "                first = p\n",
    "            last = p\n",
    "            p = p.right\n",
    "        first.left = last\n",
    "        last.right = first\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        stack = []\n",
    "        pre = head = None\n",
    "        cur = root\n",
    "\n",
    "        while stack or cur:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                # 中序逻辑\n",
    "                if not pre:\n",
    "                    head = cur\n",
    "                else:\n",
    "                    pre.right = cur\n",
    "                    cur.left = pre\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "        \n",
    "        head.left = pre\n",
    "        pre.right = head\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root : return root\n",
    "        stack=[]\n",
    "        head,pre,cur=None,None,root\n",
    "        while 1:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.left\n",
    "            elif stack:\n",
    "                cur=stack.pop(-1)\n",
    "                if not head:\n",
    "                    head=cur\n",
    "                else:\n",
    "                    pre.right,cur.left=cur,pre\n",
    "                pre=cur\n",
    "                cur=cur.right\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        head.left,pre.right=pre,head\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        head = root\n",
    "        pre = None\n",
    "\n",
    "        cur = root\n",
    "        stack = []\n",
    "\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "\n",
    "            cur = stack.pop()\n",
    "\n",
    "            if not pre:\n",
    "                head = cur\n",
    "            else:\n",
    "                pre.right = cur\n",
    "                cur.left = pre\n",
    "\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "\n",
    "        # Handle head node\n",
    "        head.left = pre\n",
    "        # Handle tail node\n",
    "        pre.right = head\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        stack = []\n",
    "        cur = root\n",
    "        res = []\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            tmp = stack.pop()\n",
    "            res.append(tmp)\n",
    "            cur = tmp.right\n",
    "        \n",
    "        # head = Node(0)\n",
    "        # head.right = res[0]\n",
    "        n = len(res)\n",
    "        for i in range(n):\n",
    "            res[i].right = res[(i + 1) % n]\n",
    "            res[i].left = res[(i - 1) % n]\n",
    "        return res[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        if not root.left and not root.right:\n",
    "            root.left = root.right = root\n",
    "            return root\n",
    "        queue, res = collections.deque(), [0] * 2001\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            res[queue[0].val + 1000] = queue[0]\n",
    "            if queue[0].left: queue.append(queue[0].left)\n",
    "            if queue[0].right: queue.append(queue[0].right)\n",
    "            queue.popleft()\n",
    "        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "        findhead = False\n",
    "        while i != j:\n",
    "            if i > 2000:\n",
    "                i -= 2001\n",
    "                findhead = True\n",
    "            if not first:\n",
    "                if res[i]:\n",
    "                    first = res[i]\n",
    "                    now.right = first\n",
    "                    first.left = now\n",
    "                    if findhead:\n",
    "                        head = first\n",
    "                        findhead = False\n",
    "                    i += 1\n",
    "                    continue\n",
    "            if res[i]:\n",
    "                now = first\n",
    "                first = res[i]\n",
    "                now.right = first\n",
    "                first.left = now\n",
    "                if findhead:\n",
    "                    head = first\n",
    "                    findhead = False\n",
    "            i += 1\n",
    "        first.right = root\n",
    "        root.left = first\n",
    "        if findhead: head = root\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = []\n",
    "        head = Node(0)\n",
    "        cur_head = head\n",
    "        while root or stack:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                top = stack.pop(-1)\n",
    "                cur_head.right = top\n",
    "                top.left = cur_head\n",
    "                cur_head = cur_head.right\n",
    "                root = top.right\n",
    "        tail = head\n",
    "        while tail.right:\n",
    "            tail = tail.right\n",
    "        head = head.right\n",
    "        tail.right = head\n",
    "        head.left = tail\n",
    "        return head\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = []\n",
    "        head = Node(0)\n",
    "        cur_head = head\n",
    "        while stack or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop(-1)\n",
    "                cur_head.right = root\n",
    "                root.left = cur_head\n",
    "                cur_head = cur_head.right\n",
    "                # re.append(root.val)\n",
    "                root = root.right\n",
    "        tail = head.right\n",
    "        while tail.right:\n",
    "            tail = tail.right\n",
    "        head = head.right\n",
    "        tail.right = head\n",
    "        head.left = tail\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return root\n",
    "        node_list = [[root]]\n",
    "        while True:\n",
    "            current_node_list = node_list[-1]\n",
    "            next_node_list = list()\n",
    "            for node in current_node_list:\n",
    "                if node.left != None:\n",
    "                    next_node_list.append(node.left)\n",
    "                if node.right != None:\n",
    "                    next_node_list.append(node.right)\n",
    "            if len(next_node_list) != 0:\n",
    "                node_list.append(next_node_list)\n",
    "            else:\n",
    "                break\n",
    "        sorted_node_list = list()\n",
    "        for nodes in node_list:\n",
    "            sorted_node_list += nodes\n",
    "        sorted_node_list = sorted(sorted_node_list, key=lambda x:x.val)\n",
    "\n",
    "        for i in range(len(sorted_node_list)):\n",
    "            sorted_node_list[i].right = sorted_node_list[(i + 1)%len(sorted_node_list)]\n",
    "            sorted_node_list[i].left = sorted_node_list[i - 1]\n",
    "        return sorted_node_list[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return root\n",
    "\n",
    "        deque = collections.deque()\n",
    "        deque.append(root)\n",
    "        dic = []\n",
    "\n",
    "        while deque:\n",
    "            cur = deque.pop()\n",
    "            if cur.left: deque.append(cur.left)\n",
    "            if cur.right: deque.append(cur.right)\n",
    "            dic.append([cur.val, cur])\n",
    "        \n",
    "        dic = sorted(dic, key=lambda x: x[0])\n",
    "        n = len(dic)\n",
    "        for i, item in enumerate(dic):\n",
    "            item[1].left = dic[i-1][1]\n",
    "            item[1].right = dic[(i+1)%n][1]\n",
    "        \n",
    "        return dic[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return root\n",
    "\n",
    "        deque = collections.deque()\n",
    "        deque.append(root)\n",
    "        dic = []\n",
    "\n",
    "        while deque:\n",
    "            cur = deque.pop()\n",
    "            if cur.left: deque.append(cur.left)\n",
    "            if cur.right: deque.append(cur.right)\n",
    "            dic.append([cur.val, cur])\n",
    "        \n",
    "        dic = sorted(dic, key=lambda x: x[0])\n",
    "        n = len(dic)\n",
    "        for i, item in enumerate(dic):\n",
    "            item[1].left = dic[i-1][1]\n",
    "            item[1].right = dic[(i+1)%n][1]\n",
    "        \n",
    "        return dic[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def in_order(self, root):\n",
    "        node_lst = []\n",
    "        stack = [(0, root)]\n",
    "        while stack:\n",
    "            visited, node = stack.pop()\n",
    "            if node:\n",
    "                if visited:\n",
    "                    node_lst.append(Node(node.val))\n",
    "                else:\n",
    "                    stack.append([0, node.right])\n",
    "                    stack.append([1, node])\n",
    "                    stack.append([0, node.left])\n",
    "        return node_lst\n",
    "\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        node_lst = self.in_order(root)\n",
    "        i, n = 0, len(node_lst)-1\n",
    "        prev, cur = node_lst[n], node_lst[i]\n",
    "        while i <= n:\n",
    "            prev.right = cur\n",
    "            cur.left = prev\n",
    "            i += 1\n",
    "            if i > n:\n",
    "                break\n",
    "            prev = cur\n",
    "            cur = node_lst[i]\n",
    "        return node_lst[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        def dfs(node: Node, res: list):\n",
    "            if node is not None:\n",
    "                dfs(node.left, res)\n",
    "                res.append(node)\n",
    "                dfs(node.right, res)\n",
    "        res = []\n",
    "        dfs(root, res)\n",
    "        for index, node in enumerate(res):\n",
    "            if index <= len(res)-2:\n",
    "                node.right = res[index+1]\n",
    "            if index >= 1:\n",
    "                node.left = res[index-1]\n",
    "        res[0].left = res[-1]\n",
    "        res[-1].right = res[0]\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def traversal(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            traversal(root.left)\n",
    "\n",
    "            if self.prev:\n",
    "                self.prev.right = root\n",
    "                #print(root.val, self.prev.val, self.start.val)\n",
    "            else:\n",
    "                self.start = root\n",
    "                #print(root.val, self.prev, self.start.val)\n",
    "            self.prev = root\n",
    "\n",
    "            traversal(root.right)\n",
    "        \n",
    "        if not root:\n",
    "            return root\n",
    "        self.prev, self.start = None, None\n",
    "        traversal(root)\n",
    "\n",
    "        cur = self.start\n",
    "        prev = None\n",
    "        while cur:\n",
    "            cur.left = prev\n",
    "            prev = cur\n",
    "            cur = cur.right\n",
    "        \n",
    "        self.start.left = prev\n",
    "        prev.right = self.start\n",
    "        return self.start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return\n",
    "            dfs(cur.left) #递归左树\n",
    "            if self.pre: #如果前面有结点\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur #保存cur\n",
    "            dfs(cur.right) #递归右树\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.prev = None \n",
    "        self.head = None \n",
    "\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return \n",
    "        self.inOrder(root)\n",
    "        self.head.left = self.prev \n",
    "        self.prev.right = self.head \n",
    "        return self.head \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return \n",
    "        self.inOrder(root.left)\n",
    "        if self.prev:\n",
    "            self.prev.right = root \n",
    "        root.left = self.prev\n",
    "        self.prev = root  \n",
    "        if not self.head:\n",
    "            self.head = root \n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            dfs(node.left)\n",
    "            if self.pre:\n",
    "                self.pre.right,node.left=node,self.pre\n",
    "            else:\n",
    "                self.head=node\n",
    "            self.pre=node\n",
    "            dfs(node.right)\n",
    "        \n",
    "        if not root:return None\n",
    "        self.pre=None\n",
    "        dfs(root)\n",
    "        self.head.left,self.pre.right=self.pre,self.head\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = None\n",
    "        self.head = None\n",
    "    def dfs(self, root):\n",
    "        if not root: return\n",
    "        if root.left: self.dfs(root.left)\n",
    "        if self.pre:\n",
    "            self.pre.right = root\n",
    "            root.left = self.pre\n",
    "        else:\n",
    "            self.head = root\n",
    "        self.pre = root\n",
    "        if root.right: self.dfs(root.right)\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return\n",
    "        self.dfs(root)\n",
    "        self.head.left = self.pre\n",
    "        self.pre.right = self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node': \n",
    "        if not root:\n",
    "            return  \n",
    "        def dfs(cur):\n",
    "            if not cur : return  \n",
    "            dfs(cur.left) # 递归左子树 \n",
    "            if self.pre: \n",
    "                self.pre.right, cur.left = cur, self.pre \n",
    "            else:\n",
    "                self.head = cur   \n",
    "            self.pre = cur \n",
    "            dfs(cur.right) # 递归右子树  \n",
    "\n",
    "        self.pre = None \n",
    "        dfs(root)  \n",
    "        # 此时pre指向最后一个节点, 首尾相连形成循环链表 \n",
    "        self.head.left, self.pre.right = self.pre, self.head \n",
    "        return self.head \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur:return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right,cur.left=cur,self.pre\n",
    "\n",
    "            else:\n",
    "                self.head=cur\n",
    "            self.pre=cur\n",
    "            dfs(cur.right)\n",
    "        if not root:return\n",
    "        self.pre=None\n",
    "\n",
    "        dfs(root)\n",
    "        self.head.left,self.pre.right=self.pre,self.head\n",
    "        return self.head\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        head = pre = None\n",
    "        def dfs(node: 'Node') -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            nonlocal head, pre\n",
    "            if head is None:\n",
    "                head = node\n",
    "            else:\n",
    "                pre.right = node\n",
    "            node.left = pre\n",
    "            pre = node\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        head.left, pre.right = pre, head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        \n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        self.pre=None\n",
    "        self.head=None\n",
    "        self.dfs(root)\n",
    "        self.head.left,self.pre.right=self.pre,self.head\n",
    "        return self.head \n",
    "    \n",
    "    def dfs(self,node):\n",
    "        if not node: return \n",
    "        self.dfs(node.left)\n",
    "        if self.pre:\n",
    "            self.pre.right=node\n",
    "            node.left=self.pre\n",
    "        else:\n",
    "            self.head=node\n",
    "        self.pre=node\n",
    "        self.dfs(node.right)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def recur(cur):\n",
    "            if not cur: return\n",
    "            recur(cur.left)\n",
    "            if self.pre:\n",
    "                cur.left,self.pre.right=self.pre,cur\n",
    "            else:\n",
    "                self.head=cur\n",
    "            self.pre=cur\n",
    "            recur(cur.right)\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre=None\n",
    "        recur(root)\n",
    "        self.head.left=self.pre\n",
    "        self.pre.right=self.head\n",
    "        return self.head\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root :\n",
    "            return None\n",
    "\n",
    "        ans = collections.deque()\n",
    "\n",
    "        def looknode(root):\n",
    "            if not root:\n",
    "                return \n",
    "            looknode(root.left)\n",
    "            ans.append(root)\n",
    "            looknode(root.right)\n",
    "        \n",
    "        looknode(root)\n",
    "        n = len(ans)\n",
    "        for i in range(n):\n",
    "            ans[i].right = ans[i+1 if i+1 < n else 0]\n",
    "            ans[i].left =  ans[i-1 if i-1 >= 0 else n-1]\n",
    "\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def recur(cur):\n",
    "            if not cur: return\n",
    "            recur(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right=cur\n",
    "                cur.left=self.pre\n",
    "            else:\n",
    "                self.head=cur\n",
    "            self.pre=cur\n",
    "            recur(cur.right)\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre=None\n",
    "        recur(root)\n",
    "        self.head.left,self.pre.right=self.pre,self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return \n",
    "        def dfs(cur): \n",
    "            if not cur: return \n",
    "            dfs(cur.left)\n",
    "            if self.pre: \n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: \n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def post_travel(node):\n",
    "            if node is None:\n",
    "                return \n",
    "\n",
    "            post_travel(node.left)\n",
    "            post_travel(node.right)\n",
    "            \n",
    "            if node.left:\n",
    "                p = node.left\n",
    "                while p.right:\n",
    "                    p = p.right\n",
    "                node.left = p\n",
    "                p.right = node\n",
    "            \n",
    "            if node.right:\n",
    "                p = node.right\n",
    "                while p.left:\n",
    "                    p = p.left\n",
    "                node.right = p\n",
    "                p.left = node\n",
    "\n",
    "            return \n",
    "        if not root:\n",
    "            return\n",
    "        post_travel(root)\n",
    "        p = root\n",
    "        while p.left:\n",
    "            p = p.left\n",
    "        left = p\n",
    "\n",
    "        p = root\n",
    "        while p.right:\n",
    "            p = p.right\n",
    "        right = p\n",
    "\n",
    "        left.left = right\n",
    "        right.right = left\n",
    "\n",
    "        return left\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left) # 递归左子树\n",
    "            if self.pre: # 修改节点引用\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: # 记录头节点\n",
    "                self.head = cur\n",
    "            self.pre = cur # 保存 cur\n",
    "            dfs(cur.right) # 递归右子树\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return cur\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right = cur\n",
    "                self.pre.right.left = self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        if not root:\n",
    "            return root\n",
    "        self.pre = None\n",
    "        self.head = None\n",
    "        dfs(root)\n",
    "        self.head.left,self.pre.right = self.pre,self.head\n",
    "        return self.head\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root):\n",
    "        global pre, head\n",
    "        pre, head = None, None\n",
    "        def dfs(cur):\n",
    "            global pre, head\n",
    "            if not cur:\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "            if pre:\n",
    "                pre.right = cur\n",
    "                cur.left = pre\n",
    "            else:\n",
    "                head =  cur\n",
    "            pre = cur\n",
    "            dfs(cur.right)\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        dfs(root)\n",
    "        head.left = pre\n",
    "        pre.right = head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left) # 递归左子树\n",
    "            if self.pre: # 修改节点引用\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: # 记录头节点\n",
    "                self.head = cur\n",
    "            self.pre = cur # 保存 cur\n",
    "            dfs(cur.right) # 递归右子树\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(inputNode):\n",
    "            if inputNode is not None:\n",
    "                dfs(inputNode.left)\n",
    "                res.append(inputNode)\n",
    "                dfs(inputNode.right)\n",
    "        if root is None:\n",
    "            return None\n",
    "        res = []\n",
    "        dfs(root)\n",
    "        head, prev = None, None\n",
    "        for cur in iter(res):\n",
    "            if head is None:\n",
    "                head = cur\n",
    "            if prev is not None:\n",
    "                prev.right = cur\n",
    "            cur.left = prev\n",
    "            prev = cur\n",
    "        prev.right = head\n",
    "        head.left = prev\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        # if not root: return None\n",
    "        # stack = []\n",
    "        # node = root\n",
    "        # while node.left:\n",
    "        #     stack.append(node)\n",
    "        #     node = node.left\n",
    "        # head = Node(-1, right=node)\n",
    "        # pre_node = head\n",
    "        # while node or stack:\n",
    "        #     if node:\n",
    "        #         stack.append(node)\n",
    "        #         node = node.left\n",
    "        #     else:\n",
    "        #         node = stack.pop()\n",
    "        #         pre_node.right = node\n",
    "        #         node.left = pre_node\n",
    "        #         pre_node = node\n",
    "        #         node = node.right\n",
    "        #         if not node and not stack:\n",
    "        #             pre_node.right = head.right\n",
    "        #             head.right.left = pre_node\n",
    "        # return head.right\n",
    "\n",
    "\n",
    "\n",
    "        # 结果链表尾插 >> 循环链表\n",
    "        self.dummyHead = None\n",
    "        self.dfs(root)\n",
    "        if not self.dummyHead: return # 需要考虑空\n",
    "        self.dummyHead.left = self.tail\n",
    "        self.tail.right = self.dummyHead \n",
    "\n",
    "        return self.dummyHead\n",
    "    def dfs(self, root):\n",
    "        if not root: return\n",
    "        self.dfs(root.left)\n",
    "        x = root\n",
    "\n",
    "        if not self.dummyHead:\n",
    "            self.dummyHead = x\n",
    "            self.tail = self.dummyHead\n",
    "        else:\n",
    "            self.tail.right = x\n",
    "            x.left = self.tail\n",
    "            self.tail = x\n",
    "\n",
    "        self.dfs(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            # 递归左子树\n",
    "            dfs(cur.left)\n",
    "            # 构建索引\n",
    "            if self.pre:\n",
    "                self.pre.right = cur\n",
    "                cur.left = self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        \n",
    "        if not root: return None\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        dump = Node()\n",
    "        dump.right = root\n",
    "        pre = dump\n",
    "        def mid(node):\n",
    "            nonlocal pre\n",
    "            if not node:\n",
    "                return\n",
    "            mid(node.left)\n",
    "            pre.right = node\n",
    "            node.left = pre\n",
    "            pre = node\n",
    "            mid(node.right)\n",
    "        mid(root)\n",
    "        # 首尾相连\n",
    "        pre.right = dump.right\n",
    "        dump.right.left = pre\n",
    "        return dump.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        head = Node()\n",
    "        head.right = root\n",
    "        pre = head\n",
    "        def midOrder(node):\n",
    "            nonlocal pre\n",
    "            if not node:\n",
    "                return\n",
    "            midOrder(node.left)\n",
    "            # vis\n",
    "            pre.right = node\n",
    "            node.left = pre\n",
    "            pre = node\n",
    "            midOrder(node.right)\n",
    "\n",
    "        midOrder(root)\n",
    "        # 处理头尾节点\n",
    "        head.right.left = pre\n",
    "        pre.right = head.right\n",
    "        return head.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: \n",
    "                return \n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right, cur.left = cur, self.pre \n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "\n",
    "        if not root: return\n",
    "        self.pre = None \n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        self.pre = None\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left)\n",
    "            if self.pre: self.pre.right, cur.left = cur, self.pre\n",
    "            else: self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n",
    "            \n",
    "            \n",
    "\n",
    "#        if not root.left and not root.right:\n",
    "#            root.left = root.right = root\n",
    "#            return root\n",
    "#        queue, res = collections.deque(), [0] * 2001\n",
    "#        queue.append(root)\n",
    "#        while queue:\n",
    "#            res[queue[0].val + 1000] = queue[0]\n",
    "#            if queue[0].left: queue.append(queue[0].left)\n",
    "#            if queue[0].right: queue.append(queue[0].right)\n",
    "#            queue.popleft()\n",
    "#        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "#        findhead = False\n",
    "#        while i != j:\n",
    "#            if i > 2000:\n",
    "#                i -= 2001\n",
    "#                findhead = True\n",
    "#            if not first:\n",
    "#                if res[i]:\n",
    "#                    first = res[i]\n",
    "#                    now.right = first\n",
    "#                    first.left = now\n",
    "#                    if findhead:\n",
    "#                        head = first\n",
    "#                        findhead = False\n",
    "#                    i += 1\n",
    "#                    continue\n",
    "#            if res[i]:\n",
    "#                now = first\n",
    "#                first = res[i]\n",
    "#                now.right = first\n",
    "#                first.left = now\n",
    "#                if findhead:\n",
    "#                    head = first\n",
    "#                    findhead = False\n",
    "#            i += 1\n",
    "#        first.right = root\n",
    "#        root.left = first\n",
    "#        if findhead: head = root\n",
    "#        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        self.pre = None\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left)\n",
    "            if self.pre: self.pre.right, cur.left = cur, self.pre\n",
    "            else: self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n",
    "            \n",
    "            \n",
    "\n",
    "#        if not root.left and not root.right:\n",
    "#            root.left = root.right = root\n",
    "#            return root\n",
    "#        queue, res = collections.deque(), [0] * 2001\n",
    "#        queue.append(root)\n",
    "#        while queue:\n",
    "#            res[queue[0].val + 1000] = queue[0]\n",
    "#            if queue[0].left: queue.append(queue[0].left)\n",
    "#            if queue[0].right: queue.append(queue[0].right)\n",
    "#            queue.popleft()\n",
    "#        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "#        findhead = False\n",
    "#        while i != j:\n",
    "#            if i > 2000:\n",
    "#                i -= 2001\n",
    "#                findhead = True\n",
    "#            if not first:\n",
    "#                if res[i]:\n",
    "#                    first = res[i]\n",
    "#                    now.right = first\n",
    "#                    first.left = now\n",
    "#                    if findhead:\n",
    "#                        head = first\n",
    "#                        findhead = False\n",
    "#                    i += 1\n",
    "#                    continue\n",
    "#            if res[i]:\n",
    "#                now = first\n",
    "#                first = res[i]\n",
    "#                now.right = first\n",
    "#                first.left = now\n",
    "#                if findhead:\n",
    "#                    head = first\n",
    "#                    findhead = False\n",
    "#            i += 1\n",
    "#        first.right = root\n",
    "#        root.left = first\n",
    "#        if findhead: head = root\n",
    "#        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        \n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return\n",
    "\n",
    "            # 递归左子树\n",
    "            dfs(cur.left)\n",
    "            \n",
    "            # 修改节点引用\n",
    "            if self.pre:\n",
    "                self.pre.right = cur\n",
    "                cur.left = self.pre\n",
    "            else:\n",
    "                # 记录头结点\n",
    "                self.head = cur\n",
    "\n",
    "            # 保存上一节点\n",
    "            self.pre = cur\n",
    "\n",
    "            # 递归右子树\n",
    "            dfs(cur.right)\n",
    "        if not root:\n",
    "            return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        # 设定前驱节点\n",
    "        self.head.left = self.pre\n",
    "        # 设定后继节点\n",
    "        self.pre.right = self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            # 递归左子树\n",
    "            dfs(cur.left)\n",
    "            # 构建索引\n",
    "            if self.pre:\n",
    "                self.pre.right = cur\n",
    "                cur.left = self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        \n",
    "        if not root: return None\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        dump = Node()\n",
    "        dump.right = root\n",
    "        pre = dump\n",
    "        def mid(node):\n",
    "            nonlocal pre\n",
    "            if not node:\n",
    "                return\n",
    "            mid(node.left)\n",
    "            pre.right = node\n",
    "            node.left = pre\n",
    "            pre = node\n",
    "            mid(node.right)\n",
    "        mid(root)\n",
    "        # 首尾相连\n",
    "        pre.right = dump.right\n",
    "        dump.right.left = pre\n",
    "        return dump.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: \n",
    "                return\n",
    "            dfs(cur.left) # 递归左子树\n",
    "            if self.pre: # 修改节点引用\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: # 记录头节点\n",
    "                self.head = cur\n",
    "            self.pre = cur # 保存 cur\n",
    "            dfs(cur.right) # 递归右子树\n",
    "        \n",
    "        if not root: \n",
    "            return\n",
    "        self.pre = None\n",
    "        self.head = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur:return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right, cur.left = cur, self.pre \n",
    "            else:\n",
    "                self.head = cur \n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        \n",
    "        if not root:return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left , self.pre.right = self.pre, self.head\n",
    "        return self.head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                # 交换\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: \n",
    "                # 存下头指针\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "\n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        # 头尾连接\n",
    "        self.pre.right = self.head\n",
    "        self.head.left = self.pre\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        if not root:\n",
    "            return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur:return \n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right,cur.left = cur,self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        if not root:return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left,self.pre.right = self.pre,self.head\n",
    "        return self.head\n",
    "\n",
    "# class Solution:\n",
    "#     def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "#         def dfs(cur):\n",
    "#             if not cur: return\n",
    "#             dfs(cur.left) # 递归左子树\n",
    "#             if self.pre: # 修改节点引用\n",
    "#                 self.pre.right, cur.left = cur, self.pre\n",
    "#             else: # 记录头节点\n",
    "#                 self.head = cur\n",
    "#             self.pre = cur # 保存 cur\n",
    "#             dfs(cur.right) # 递归右子树\n",
    "        \n",
    "#         if not root: return\n",
    "#         self.pre = None\n",
    "#         dfs(root)\n",
    "#         self.head.left, self.pre.right = self.pre, self.head\n",
    "#         return self.head\n",
    "\n",
    "# 作者：Krahets\n",
    "# 链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/lxh893/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        self.pre = None      \n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right = cur\n",
    "                cur.left = self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        if not root:\n",
    "            return\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right=self.pre,self.head\n",
    "        return self.head\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        \n",
    "        if not root:return \n",
    "\n",
    "        pre, head = None, None\n",
    "        def dfs(r):\n",
    "            nonlocal pre,head\n",
    "            if not r: return \n",
    "            dfs(r.left)\n",
    "            if pre:\n",
    "                pre.right, r.left = r, pre\n",
    "            else:\n",
    "                head = r\n",
    "            pre = r\n",
    "            dfs(r.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        head.left, pre.right = pre, head\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left) \n",
    "            if self.pre: \n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: \n",
    "                self.head = cur\n",
    "            self.pre = cur \n",
    "            dfs(cur.right) \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root: return None\n",
    "        self.pre = None\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left)\n",
    "            if self.pre: self.pre.right, cur.left = cur, self.pre\n",
    "            else: self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n",
    "            \n",
    "            \n",
    "\n",
    "#        if not root.left and not root.right:\n",
    "#            root.left = root.right = root\n",
    "#            return root\n",
    "#        queue, res = collections.deque(), [0] * 2001\n",
    "#        queue.append(root)\n",
    "#        while queue:\n",
    "#            res[queue[0].val + 1000] = queue[0]\n",
    "#            if queue[0].left: queue.append(queue[0].left)\n",
    "#            if queue[0].right: queue.append(queue[0].right)\n",
    "#            queue.popleft()\n",
    "#        now, i, j, first, head = root, root.val + 1001, root.val + 1000, None, None\n",
    "#        findhead = False\n",
    "#        while i != j:\n",
    "#            if i > 2000:\n",
    "#                i -= 2001\n",
    "#                findhead = True\n",
    "#            if not first:\n",
    "#                if res[i]:\n",
    "#                    first = res[i]\n",
    "#                    now.right = first\n",
    "#                    first.left = now\n",
    "#                    if findhead:\n",
    "#                        head = first\n",
    "#                        findhead = False\n",
    "#                    i += 1\n",
    "#                    continue\n",
    "#            if res[i]:\n",
    "#                now = first\n",
    "#                first = res[i]\n",
    "#                now.right = first\n",
    "#                first.left = now\n",
    "#                if findhead:\n",
    "#                    head = first\n",
    "#                    findhead = False\n",
    "#            i += 1\n",
    "#        first.right = root\n",
    "#        root.left = first\n",
    "#        if findhead: head = root\n",
    "#        return head"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
